#ifndef _SORT_H_
#define _SORT_H_

#include "Object.h"
#include "Exception.h"
#include "Array.h"

namespace MySTL
{

class Sort : public Object
{
public:
	enum SortPosition
	{
		Min2Max,
		Max2Min,

		SORT_POS_COUNT,
	};

public:
	template < typename T >
	static void select(T* array, int len, SortPosition sortPos = Min2Max);
	template < typename T >
	static void select(Array<T>& array, SortPosition sortPos = Min2Max);

	template < typename T >
	static void insert(T* array, int len, SortPosition sortPos = Min2Max);
	template < typename T >
	static void insert(Array<T>& array, SortPosition sortPos = Min2Max);

	template < typename T >
	static void bubble(T* array, int len, SortPosition sortPos = Min2Max);
	template < typename T >
	static void bubble(Array<T>& array, SortPosition sortPos = Min2Max);

	template < typename T >
	static void shell(T* array, int len, SortPosition sortPos = Min2Max);
	template < typename T >
	static void shell(Array<T>& array, SortPosition sortPos = Min2Max);

	template < typename T >
	static void merge(T* array, int len, SortPosition sortPos = Min2Max);
	template < typename T >
	static void merge(Array<T>& array, SortPosition sortPos = Min2Max);

	template < typename T >
	static void quick(T* array, int len, SortPosition sortPos = Min2Max);
	template < typename T >
	static void quick(Array<T>& array, SortPosition sortPos = Min2Max);

protected:
	template < typename T >
	static void merge(T* array, T* buf, int begin, int end, SortPosition sortPos);
	template < typename T >
	static void merge(T* array, T* buf, int begin, int mid, int end, SortPosition sortPos);
	template < typename T >
	static void quick(T* array, int begin, int end, SortPosition sortPos);

protected:
	template < typename T >
	static void swap(T& a, T& b);
};

template < typename T >
void Sort::select(T* array, int len, SortPosition sortPos)
{
	if (NULL == array || len <= 0 || sortPos < 0 || sortPos >= SORT_POS_COUNT)
	{
		THROW_EXCEPTION(ParameterErrorException, "Parameter error in static void Sort::select(T* array, int len, SortPosition sortPos)");
	}

	for (int i = 0; i < len; ++i)
	{
		int index = i;
		for (int j = i + 1; j < len; ++j)
		{
			if (sortPos == Min2Max ? array[j] < array[index] : array[j] > array[index])
			{
				index = j;
			}
		}
		if (index != i)
		{
			swap(array[index], array[i]);
		}
	}
}

template < typename T >
void Sort::select(Array<T>& array, SortPosition sortPos)
{
	return select(array.getArray(), array.length(), sortPos);
}

template < typename T >
void Sort::insert(T* array, int len, SortPosition sortPos)
{
	if (NULL == array || len <= 0 || sortPos < 0 || sortPos >= SORT_POS_COUNT)
	{
		THROW_EXCEPTION(ParameterErrorException, "Parameter error in static void Sort::insert(T* array, int len, SortPosition sortPos)");
	}

	for (int i = 1; i < len; ++i)
	{
		for (int j = i; j > 0; --j)
		{
			if (sortPos == Min2Max ? array[j - 1] > array[j] : array[j - 1] < array[j])
			{
				swap(array[j - 1], array[j]);
			}
			else
			{
				break;
			}
		}
	}
}

template < typename T >
void Sort::insert(Array<T>& array, SortPosition sortPos)
{
	return insert(array.getArray(), array.length(), sortPos);
}

template < typename T >
void Sort::bubble(T* array, int len, SortPosition sortPos)
{
	if (NULL == array || len <= 0 || sortPos < 0 || sortPos >= SORT_POS_COUNT)
	{
		THROW_EXCEPTION(ParameterErrorException, "Parameter error in static void Sort::bubble(T* array, int len, SortPosition sortPos)");
	}

	bool exchange = true;
	for (int i = 0; i < len && exchange; ++i)
	{
		exchange = false;
		for (int j = 0; j < len - i - 1; ++j)
		{
			if (sortPos == Min2Max ? array[j] > array[j + 1] : array[j] < array[j + 1])
			{
				swap(array[j], array[j + 1]);
				exchange = true;
			}
		}
	}
}

template < typename T >
void Sort::bubble(Array<T>& array, SortPosition sortPos)
{
	return bubble(array.getArray(), array.length(), sortPos);
}

template < typename T >
void Sort::shell(T* array, int len, SortPosition sortPos)
{
	if (NULL == array || len <= 0 || sortPos < 0 || sortPos >= SORT_POS_COUNT)
	{
		THROW_EXCEPTION(ParameterErrorException, "Parameter error in static void Sort::shell(T* array, int len, SortPosition sortPos)");
	}

	int d = len;

	do
	{
		d = d / 3 + 1;

		for (int k = 0; k < d; ++k)
		{
			for (int i = k + d; i < len; i+=d)
			{
				for (int j = i; j >= d; j-=d)
				{
					if (sortPos == Min2Max ? array[j - d] > array[j] : array[j - d] < array[j])
					{
						swap(array[j - d], array[j]);
					}
					else
					{
						break;
					}
				}
			}
		}
	} while (d > 1);
}

template < typename T >
void Sort::shell(Array<T>& array, SortPosition sortPos)
{
	return shell(array.getArray(), array.length(), sortPos);
}

template < typename T >
void Sort::merge(T* array, int len, SortPosition sortPos)
{
	if (NULL == array || len <= 0 || sortPos < 0 || sortPos >= SORT_POS_COUNT)
	{
		THROW_EXCEPTION(ParameterErrorException, "Parameter error in static void Sort::merge(T* array, int len, SortPosition sortPos)");
	}

	T* buf = new T[len];
	if (NULL != buf)
	{
		merge(array, buf, 0, len - 1, sortPos);
	}
	else
	{
		THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to sort in static void Sort::merge(T* array, int len, SortPosition sortPos)");
	}
	delete[] buf;
}

template < typename T >
void Sort::merge(Array<T>& array, SortPosition sortPos)
{
	return merge(array.getArray(), array.length(), sortPos);
}

template < typename T >
void Sort::merge(T* array, T* buf, int begin, int end, SortPosition sortPos)
{
	if (begin < end)
	{
		merge(array, buf, begin, (begin + end) / 2, sortPos);
		merge(array, buf, (begin + end) / 2 + 1, end, sortPos);
		merge(array, buf, begin, (begin + end) / 2, end, sortPos);
	}
}

template < typename T >
void Sort::merge(T* array, T* buf, int begin, int mid, int end, SortPosition sortPos)
{
	int i = begin;
	int j = mid + 1;
	int index = begin;

	while (i <= mid && j <= end)
	{
		if (sortPos == Min2Max ? array[i] <= array[j] : array[i] >= array[j])
		{
			buf[index++] = array[i++];
		}
		else
		{
			buf[index++] = array[j++];
		}
	}

	while (i <= mid)
	{
		buf[index++] = array[i++];
	}

	while (j <= end)
	{
		buf[index++] = array[j++];
	}

	for (int k = begin; k <= end; ++k)
	{
		array[k] = buf[k];
	}
}

template < typename T >
void Sort::quick(T* array, int len, SortPosition sortPos)
{
	if (NULL == array || len <= 0 || sortPos < 0 || sortPos >= SORT_POS_COUNT)
	{
		THROW_EXCEPTION(ParameterErrorException, "Parameter error in static void Sort::quick(T* array, int len, SortPosition sortPos)");
	}

	quick(array, 0, len - 1, sortPos);
}

template < typename T >
void Sort::quick(Array<T>& array, SortPosition sortPos)
{
	return quick(array.getArray(), array.length(), sortPos);
}

template < typename T >
void Sort::quick(T* array, int begin, int end, SortPosition sortPos)
{
	if (begin >= end)
	{
		return;
	}

	int i = begin;
	int j = end;
	T base = array[begin];

	while (i < j)
	{
		while (i < j && (sortPos == Min2Max ? array[j] >= base : array[j] <= base))
			--j;
		if (i != j)
			array[i] = array[j];

		while (i < j && (sortPos == Min2Max ? array[i] <= base : array[i] >= base))
			++i;
		if (i != j)
			array[j] = array[i];
	}
	array[i] = base;

	quick(array, begin, i - 1, sortPos);
	quick(array, i + 1, end, sortPos);
}

template < typename T >
void Sort::swap(T& a, T& b)
{
	T tmp = a;
	a = b;
	b = tmp;
}

}

#endif